package com.leetcode.partition2;

import java.util.Arrays;
import java.util.LinkedList;

/**
 * @author `RKC`
 * @date 2021/8/2 8:25
 */
public class LC200岛屿数量 {

    private static final int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    private static int count;

    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) return 0;
        return unionFind(grid);
    }

    public static void main(String[] args) {
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '1', '0', '0', '0'},
                {'0', '0', '1', '0', '0'},
                {'0', '0', '0', '1', '1'}
        };
//        char[][] grid = {
//                {'1', '1', '1', '1', '0'},
//                {'1', '1', '0', '1', '0'},
//                {'1', '1', '0', '0', '0'},
//                {'0', '0', '0', '0', '0'}
//        };
        System.out.println(numIslands(grid));
    }

    private static int unionFind(char[][] grid) {
        int waterCount = 0;         //记录水域数
        count = grid.length * grid[0].length;
        int[] root = new int[grid.length * grid[0].length];
        for (int i = 0; i < root.length; i++) root[i] = i;      //初始化每一个区域的根节点都是自己
        System.out.println(Arrays.toString(root));

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '0') {
                    waterCount++;
                    continue;
                }
                for (int[] dir : dirs) {
                    int neighborRow = i + dir[0], neighborCol = j + dir[1];
                    //边界值判断
                    if (neighborRow < 0 || neighborRow >= grid.length || neighborCol < 0 || neighborCol >= grid[0].length || grid[neighborRow][neighborCol] == '0') {
                        continue;
                    }
                    //将映射后的当前的岛屿与相邻岛屿合并
                    int cur = i * grid[0].length + j, neighbor = neighborRow * grid[0].length + neighborCol;
                    union(root, cur, neighbor);
                }
            }
        }
        System.out.println(Arrays.toString(root));
        return count - waterCount;          //answer=总数量-合并的陆地数-水域数
    }

    private static void union(int[] root, int x, int y) {
        int rootX = find(root, x), rootY = find(root, y);
        if (rootX != rootY) {
            root[rootY] = rootX;
            count--;                //每进行一次合并操作，陆地数就少1
        }
    }

    private static int find(int[] root, int x) {
        if (x == root[x]) return root[x];
        return find(root, root[x]);
    }

    private static int bfs(char[][] grid) {
        LinkedList<Coordinate> queue = new LinkedList<>();
        int number = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    queue.add(new Coordinate(i, j));
                    grid[i][j] = '0';
                    while (!queue.isEmpty()) {
                        Coordinate current = queue.poll();
                        int x = current.i;
                        int y = current.j;
                        if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                            grid[x - 1][y] = '0';
                            queue.add(new Coordinate(x - 1, y));
                        }
                        if (x + 1 < grid.length && grid[x + 1][y] == '1') {
                            grid[x + 1][y] = '0';
                            queue.add(new Coordinate(x + 1, y));
                        }
                        if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                            grid[x][y - 1] = '0';
                            queue.add(new Coordinate(x, y - 1));
                        }
                        if (y + 1 < grid[x].length && grid[x][y + 1] == '1') {
                            grid[x][y + 1] = '0';
                            queue.add(new Coordinate(x, y + 1));
                        }
                    }
                    number++;
                }
            }
        }
        return number;
    }

    private static class Coordinate {
        private int i;
        private int j;

        public Coordinate(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }

    private static int dfs(char[][] grid) {
        int number = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    number++;
                    //从grid[i][j]开始进行深度遍历
                    dfs(grid, i, j);
                }
            }
        }
        return number;
    }

    private static void dfs(char[][] grid, int i, int j) {
        //如果走到了一个水域或者已经走过的路地则进行回溯
        if (i >= grid.length || j >= grid[0].length || i < 0 || j < 0 || grid[i][j] == '0') return;
        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i - 1, j);
        dfs(grid, i, j - 1);
    }
}
